package daily.kou2022_0104;

public class Num234 {
    //234. 回文链表
    public boolean isPalindrome(ListNode head) {
        //找到中间节点
        ListNode mid=middleNode(head);
        //反转中间节点
        ListNode l2=reverseList(mid);
        while (l2!=null){
            if(l2.val!=head.val){
                return false;
            }
            l2=l2.next;
            head=head.next;
        }
       return true;
    }
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode sec = head.next;
        // 2.反转第二个节点之后的子链表
        ListNode newHead = reverseList(head.next);
        // 3.将sec.next = head;
        // head.next = null;
        sec.next = head;
        head.next = null;
        return newHead;
    }

    public ListNode middleNode(ListNode head) {
        // fast一次走两步
        ListNode fast = head;
        // low一次走一步
        ListNode low = head;
        // 当fast为null(偶数个节点) || fast.next == null(奇数个节点)
        while (fast != null && fast.next != null) {
            low = low.next;
            fast = fast.next.next;
        }
        return low;
    }
}
